D. GCD-sequence
给定大小为
对于
确定是否有可能从数组
Example
例如,假设 Khristina 有一个数组
得到的 GCD 序列
无想法
主要思路:
若本来就已经不递减了,这时只需要删除最后一个元素即可保证还是满足的,所以一定是满足条件的
若本来不满足,则一定至少有一个位置满足
void solve() {
int n;cin >> n;
vector<int> a(n), g(n - 1);
for (int i = 0;i < n;i++)cin >> a[i];
for (int i = 0;i < n - 1;i++)g[i] = __gcd(a[i], a[i + 1]);
if (is_sorted(g.begin(), g.end())) {
cout << "YES\n";return;
}
int idx = -1;
for (int i = 1;i < n - 1;i++) {
if (g[i - 1] > g[i]) {
idx = i;
}
}
vector<int> a1(a), a2(a), a3(a);
a1.erase(a1.begin() + idx - 1);
a2.erase(a2.begin() + idx);
a3.erase(a3.begin() + idx + 1);
vector<int> g1(n - 2), g2(n - 2), g3(n - 2);
for (int i = 0;i < n - 2;i++) {
g1[i] = __gcd(a1[i], a1[i + 1]);
g2[i] = __gcd(a2[i], a2[i + 1]);
g3[i] = __gcd(a3[i], a3[i + 1]);
}
int ok = 0;
ok += is_sorted(g1.begin(), g1.end());
ok += is_sorted(g2.begin(), g2.end());
ok += is_sorted(g3.begin(), g3.end());
if (ok) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}